//有效的括号

//typedef char STDatatype;
//
//typedef struct Stack
//{
//	STDatatype* a;
//	int top;
//	int capacity;
//}ST;
//
//
////函数声明
////函数的初始化和销毁
//void STInit(ST* pst);
//void STDestroy(ST* pst);
//
////进栈和出栈
//void STPush(ST* pst, STDatatype x);
//void STPop(ST* pst);
//
////栈顶
//STDatatype STTop(ST* pst);
//
////栈是否为空
//bool STEmpty(ST* pst);
//
////个数
//int STSize(ST* pst);
////函数的初始化和销毁
//void STInit(ST* pst)
//{
//	assert(pst);
//	pst->a = NULL;
//	pst->top = pst->capacity = 0;
//}
//void STDestroy(ST* pst)
//{
//	assert(pst);
//	free(pst->a);
//	pst->a = NULL;
//	pst->top = pst->capacity = 0;
//}
////进栈和出栈
//void STPush(ST* pst, STDatatype x)
//{
//	assert(pst);
//	if (pst->capacity == pst->top)
//	{
//		//增加容量
//		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
//		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
//		if (tmp == NULL)
//		{
//			perror("realloc");
//			exit(1);
//		}
//		pst->a = tmp;
//		pst->capacity = newcapacity;
//	}
//	pst->a[pst->top] = x;
//	pst->top++;
//}
//void STPop(ST* pst)
//{
//	assert(pst);
//	assert(pst->top > 0);
//	pst->top--;
//}
////栈顶
//STDatatype STTop(ST* pst)
//{
//	assert(pst);
//	assert(pst->top > 0);
//	return pst->a[pst->top - 1];
//}
////栈是否为空
//bool STEmpty(ST* pst)
//{
//	assert(pst);
//	return pst->top == 0;
//	//等于就是空，不等于0就是非空
//}
////个数
//int STSize(ST* pst)
//{
//	assert(pst);
//	return pst->top;
//}
//bool isValid(char* s) {
//	ST st;
//	STInit(&st);
//	while (*s != 0)
//	{
//		//左括号入栈
//		if (*s == '(' || *s == '[' || *s == '{')
//		{
//			STPush(&st, *s);
//		}
//		else
//		{
//			if (STEmpty(&st))
//			{
//				return false;
//			}
//			char top = STTop(&st);
//			STPop(&st);
//			if (top == '(' && *s != ')'
//				|| top == '{' && *s != '}'
//				|| top == '[' && *s != ']')
//			{
//				return false;
//			}
//
//		}
//		++s;
//	}
//	bool ret = STEmpty(&st);
//	return ret;
//}


//用队列实现栈

//创建节点

//typedef int QDatatype;
//typedef struct Queuenode
//{
//	QDatatype val;
//	struct Queuenode* next;
//}Qnode;
//
////定义一个结构体存放指针
//typedef struct Queue
//{
//	Qnode* phead;
//	Qnode* ptail;
//	int size;
//}Queue;
//
////队列的初始化和销毁
//void QueueInit(Queue* pq);
//void QueueDestory(Queue* pq);
//
////队列的插入和删除
//void QueuePush(Queue* pq, QDatatype x);
//void QueuePop(Queue* pq);
//
////取队列头和尾的值
//QDatatype QueueFront(Queue* pq);
//QDatatype QueueBank(Queue* pq);
//
////是否为空
//bool QueueEmpty(Queue* pq);
//
////size
//int QueueSize(Queue* pq);
//
////队列的初始化和销毁
//void QueueInit(Queue* pq)
//{
//	assert(pq);
//	pq->phead = NULL;
//	pq->ptail = NULL;
//	pq->size = 0;
//}
//void QueueDestory(Queue* pq)
//{
//	assert(pq);
//	Qnode* cur = pq->phead;
//	while (cur)
//	{
//		Qnode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	pq->phead = pq->ptail = NULL;
//	pq->size = 0;
//}
//
////队列的插入和删除
//void QueuePush(Queue* pq, QDatatype x)
//{
//	assert(pq);
//	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
//	if (newnode == NULL)
//	{
//		perror("malloc:");
//		exit(1);
//	}
//	//申请成功
//	newnode->next = NULL;
//	newnode->val = x;
//	if (pq->ptail == NULL)
//	{
//		pq->phead = pq->ptail = newnode;
//	}
//	else
//	{
//		pq->ptail->next = newnode;
//		pq->ptail = newnode;
//	}
//	pq->size++;
//}
//
//void QueuePop(Queue* pq)
//{
//	assert(pq);
//	assert(pq->size != 0);
//	//一个节点
//	if (pq->phead == pq->ptail)
//	{
//		free(pq->phead);
//		pq->phead = pq->ptail = NULL;
//	}
//	else
//	{
//		//多个节点
//		Qnode* next = pq->phead->next;
//		free(pq->phead);
//		pq->phead = next;
//	}
//	pq->size--;
//}
//
////取队列头和尾的值
//QDatatype QueueFront(Queue* pq)
//{
//	assert(pq);
//	assert(pq->phead);
//	return pq->phead->val;
//}
//QDatatype QueueBank(Queue* pq)
//{
//	assert(pq);
//	assert(pq->ptail);
//	return pq->ptail->val;
//}
//
////是否为空
//bool QueueEmpty(Queue* pq)
//{
//	assert(pq);
//	return pq->size == 0;
//}
//
////size
//int QueueSize(Queue* pq)
//{
//	assert(pq);
//	return pq->size;
//}
//
////匿名结构体
//typedef struct {
//	Queue q1;
//	Queue q2;
//} MyStack;
//
//
//MyStack* myStackCreate() {
//	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
//	QueueInit(&(obj->q1));
//	QueueInit(&(obj->q2));
//	return obj;
//}
//
//void myStackPush(MyStack* obj, int x) {
//	if (!QueueEmpty(&(obj->q1)))
//	{
//		QueuePush(&(obj->q1), x);
//	}
//	else
//	{
//		QueuePush(&(obj->q2), x);
//	}
//}
//
//int myStackPop(MyStack* obj) {
//	Queue* empty = &(obj->q1);
//	Queue* noempty = &(obj->q2);
//	if (!QueueEmpty(&(obj->q1)))
//	{
//		empty = &(obj->q2);
//		noempty = &(obj->q1);
//	}
//	while (QueueSize(noempty) > 1)
//	{
//		QueuePush(empty, QueueFront(noempty));
//		QueuePop(noempty);
//	}
//	int top = QueueFront(noempty);
//	QueuePop(noempty);
//	return top;
//}
//
//int myStackTop(MyStack* obj) {
//	if (!QueueEmpty(&(obj->q1)))
//	{
//		return QueueBank(&(obj->q1));
//	}
//	else
//	{
//		return QueueBank(&(obj->q2));
//	}
//}
//
//bool myStackEmpty(MyStack* obj) {
//	return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
//}
//
//void myStackFree(MyStack* obj) {
//	QueueDestory(&(obj->q1));
//	QueueDestory(&(obj->q2));
//	free(obj);
//}


//用栈实现队列


//
//typedef int STDatatype;
//
//typedef struct Stack
//{
//	STDatatype* a;
//	int top;
//	int capacity;
//}ST;
//
////函数声明
////函数的初始化和销毁
//void STInit(ST* pst);
//void STDestroy(ST* pst);
//
////进栈和出栈
//void STPush(ST* pst, STDatatype x);
//void STPop(ST* pst);
//
////栈顶
//STDatatype STTop(ST* pst);
//
////栈是否为空
//bool STEmpty(ST* pst);
//
////个数
//int STSize(ST* pst);
//
//
////函数的初始化和销毁
//void STInit(ST* pst)
//{
//	assert(pst);
//	pst->a = NULL;
//	pst->top = pst->capacity = 0;
//}
//
//
//void STDestroy(ST* pst)
//{
//	assert(pst);
//	free(pst->a);
//	pst->a = NULL;
//	pst->top = pst->capacity = 0;
//}
//
////进栈和出栈
//void STPush(ST* pst, STDatatype x)
//{
//	assert(pst);
//	if (pst->capacity == pst->top)
//	{
//		//增加容量
//		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
//		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
//		if (tmp == NULL)
//		{
//			perror("realloc");
//			exit(1);
//		}
//		pst->a = tmp;
//		pst->capacity = newcapacity;
//	}
//	pst->a[pst->top] = x;
//	pst->top++;
//}
//void STPop(ST* pst)
//{
//	assert(pst);
//	assert(pst->top > 0);
//	pst->top--;
//}
//
////栈顶
//STDatatype STTop(ST* pst)
//{
//	assert(pst);
//	assert(pst->top > 0);
//	return pst->a[pst->top - 1];
//}
//
////栈是否为空
//bool STEmpty(ST* pst)
//{
//	assert(pst);
//	return pst->top == 0;
//	//等于就是空，不等于0就是非空
//}
//
////个数
//int STSize(ST* pst)
//{
//	assert(pst);
//	return pst->top;
//}
//
//typedef struct {
//	ST pushst;
//	ST popst;
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
//	STInit(&obj->pushst);
//	STInit(&obj->popst);
//	return obj;
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//	STPush(&obj->pushst, x);
//}
//
//
//int myQueuePeek(MyQueue* obj) {
//	if (STEmpty(&obj->popst))
//	{
//		while (!STEmpty(&obj->pushst))
//		{
//			STPush(&obj->popst, STTop(&obj->pushst));
//			STPop(&obj->pushst);
//		}
//	}
//	return STTop(&obj->popst);
//}
//
//int myQueuePop(MyQueue* obj) {
//	int f = myQueuePeek(obj);
//	STPop(&obj->popst);
//	return f;
//}
//
//bool myQueueEmpty(MyQueue* obj) {
//	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
//}
//
//void myQueueFree(MyQueue* obj) {
//	STDestroy(&obj->popst);
//	STDestroy(&obj->pushst);
//	free(obj);
//}

